首页 > 试题广场 >

斐波那契数列

[编程题]斐波那契数列
  • 热度指数：15454 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。
斐波那契数列是一个满足 的数列
数据范围：
要求：空间复杂度 ，时间复杂度 ，本题也有时间复杂度 的解法


输入描述:
仅输入一个正整数 n。


输出描述:
输出斐波那契数列中第 n 个数。
示例1

输入

4

输出

3

说明

根据斐波那契数列的定义可知，fib(1)=1,fib(2)=1,fib(3)=fib(3-1)+fib(3-2)=2,fib(4)=fib(4-1)+fib(4-2)=3，所以答案为3。 
示例2

输入

1

输出

1
示例3

输入

2

输出

1
算法知识视频讲解
添加回答
Python 3
牛客嗷嗷头像 牛客嗷嗷 
a, b = 0, 1
n = int(input())
for _ in range(n):
    a, b = b, a + b
print(a)

发表于 2022-09-13 14:41:52 回复(1)
Python 3
牛客253248209号头像 牛客253248209号 
n =  int(input())
l = [1,1]
if n <=2 :
    print(1)
else:
    for i in range(3,n+1):
        c = l[-1]+l[-2]
        l.append(c)
    print(l[-1])


发表于 2022-08-29 21:41:54 回复(0)
Python 3
壮壮kkk头像 壮壮kkk 
def fib(x):
    if x == 1&nbs***bsp;x == 2:
        return 1
    else:
        return fib(x-1) + fib(x-2)
x = int(input().strip())
print(fib(x))
这个咋超时了呢 QAQ

发表于 2022-08-28 22:44:31 回复(0)
Python 3
踏实的大白菜说又不是不能用头像 踏实的大白菜说又不是不能用 
def fob(n):
    if n <= 2:
        return 1
    dp = [0] * n
    dp[0] = 1 
    dp[1] = 1
    for i in range(2,n):
        dp[i]= dp[i-1] + dp[i-2]
    return dp[n-1]
n = int(input())
print(fob(n))

发表于 2022-08-02 00:31:21 回复(0)
Python 3
牛客659290085号头像 牛客659290085号 

n= int(input())
if n==1:
    print(1)
elif n==2:
    print(1)
elif n>=3:
    fis=[0 for i in range(n+1)]
    fis[1]=1
    fis[2]=1
    for i  in range(3,n+1):
        fis[i]=fis[i-1]+fis[i-2]
    print(fis[n])

发表于 2022-07-05 18:33:58 回复(0)
Python 3
牛客627078881号头像 牛客627078881号 
while True:
    try:
        s = int(input())
        s1, s2, s3 = 1, 0, 0
        for i in range(1, s):
            s3 = s3 + s2
            s2 = s1
            s1 = s3
        print(s1 + s2 + s3)
    except EOFError:
        break

发表于 2022-06-02 22:33:54 回复(0)
Python 3
牛客747506486号头像 牛客747506486号 
n=int(input())
dp=[1]*2
switch=0
for i in range(3,n+1):
    dp[switch]=dp[0]+dp[1]
    switch=(switch+1)%2
print(dp[(switch+1)%2])

发表于 2022-05-09 13:25:57 回复(0)
Python 3
牛客395635779号头像 牛客395635779号
n = int(input())

def fib(x):
    if x == 1 or x == 2:
        return 1
#     return fib(x-1) + fib(x-2)
    p = 1
    q = 1
    for i in range(3, n+1):
        sum = p + q
        p = q
        q = sum
    return sum

print(fib(n))
发表于 2022-04-22 21:31:52 回复(0)
Python 3
牛客a/b头像 牛客a/b
递归方程超时，只能动态规划 
n=int(input())
arr=[1 for i in range(n)]
for i in range(2,n):
    arr[i]=arr[i-1]+arr[i-2]
print(arr[-1])


发表于 2022-04-11 00:09:59 回复(0)
Python 3
lanskeep头像 lanskeep
n = int(input())

num = 1
l1 = 1
l2 = 1
t = 0

while n>=1:
    if n==1 or n==2:
        print(num)
        break
    else:
        num = l1+l2
        t = l1
        l1 = l2
        l2 = t + l2
        n-=1
发表于 2022-03-10 22:23:44 回复(0)
提交观点

问题信息

动态规划 记忆化搜索 快速幂 递归
难度：
11条回答 2597浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号